#include<bits/stdc++.h>
#define ll long long 
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef set<int>::iterator IT;
typedef pair<int,int> pii;
#define x first
#define y second
const int N=1e5+10;
int E[N],R[N];
 
struct seg{
	int mx[N<<2],tag[N<<2];ll s[N<<2];
	int a,b,c;
	#define ls (x<<1)
	#define rs (x<<1|1)
	#define mid ((l+r)>>1)
	void build(int x,int l,int r){
		if(l==r){mx[x]=R[l],s[x]=E[l];return;}
		build(ls,l,mid),build(rs,mid+1,r);
		mx[x]=max(mx[ls],mx[rs]);
		s[x]=s[ls]+s[rs];
	}
	void push_down(int x,int l,int r){
		if(!tag[x])return;
		s[x]+=1ll*(r-l+1)*tag[x];
		if(l<r)tag[ls]+=tag[x],tag[rs]+=tag[x];
		tag[x]=0;
	}
	ll sum(int x,int l,int r){
		push_down(x,l,r);
		if(a<=l&&r<=b)return s[x];
		return(a<=mid?sum(ls,l,mid):0)+(b>mid?sum(rs,mid+1,r):0);
	}
	void change(int x,int l,int r){
		if(l==r){mx[x]=c;return;}
		(a<=mid?change(ls,l,mid):change(rs,mid+1,r));
		mx[x]=max(mx[ls],mx[rs]);
	}
	void set(int x,int l,int r){
		push_down(x,l,r);
		if(l==r){s[x]=c;return;}
		(a<=mid?set(ls,l,mid):push_down(ls,l,mid));
		(a>mid?set(rs,mid+1,r):push_down(rs,mid+1,r));
		s[x]=s[ls]+s[rs];
	}
	int qry(int x,int l,int r){
		push_down(x,l,r);
		if(l==r)return s[x];
		return(a<=mid?qry(ls,l,mid):qry(rs,mid+1,r));
	}
	int find_L(int x,int l,int r){
		if(a<=l&&r<=b){
			if(l==r)return mx[x]>=c?l:0;
			return(mx[rs]>=c?find_L(rs,mid+1,r):find_L(ls,l,mid));
		} else{
			if(b>mid){
				int t=find_L(rs,mid+1,r);
				if(t)return t;
			}
			if(a<=mid)return find_L(ls,l,mid);
			return 0;
		}
	}
	int find_R(int x,int l,int r){
		if(a<=l&&r<=b){
			if(l==r)return mx[x]>=c?l:0;
			return(mx[ls]>=c?find_R(ls,l,mid):find_R(rs,mid+1,r));
		} else{
			if(a<=mid){
				int t=find_R(ls,l,mid);
				if(t)return t;
			}
			if(b>mid)return find_R(rs,mid+1,r);
			return 0;
		}
	}
	void add(int x,int l,int r){
		if(a<=l&&r<=b){tag[x]+=c,push_down(x,l,r);return;}
		push_down(x,l,r);
		if(a<=mid)add(ls,l,mid);else push_down(ls,l,mid);
		if(b>mid)add(rs,mid+1,r);else push_down(rs,mid+1,r);
		s[x]=s[ls]+s[rs];
	}
}T;
 
int n,k;
set<int>s;
void init(){
	static pii a[N];
	rep(i,n)a[i]=mp(R[i],i);
	sort(a+1,a+n+1);reverse(a+1,a+n+1);
	rep(i,n){
		int x=a[i].y;
		IT it=s.insert(x).x;
		int t1=0,t2=0;
		if(it !=s.begin())it--,t1=*it,it++;
		it++;if(it !=s.end())t2=*it;
		if(!t1&&!t2)E[x]=0;
		else if(t1&&(!t2||R[t1]<R[t2]))E[x]=R[t1]==R[x]?E[t1]:E[t1]+1;
		else E[x]=R[t2]==R[x]?E[t2]:E[t2]+1;
	}
}
inline int Q(int x){T.a=x;return T.qry(1,1,n);}
int cal(int x){
	T.a=1,T.b=x-1,T.c=R[x];
	int t1=T.a<=T.b?T.find_L(1,1,n):0;
	T.a=x+1,T.b=n,T.c=R[x];
	int t2=T.a<=T.b?T.find_R(1,1,n):0;
	
	if(!t1&&!t2)return 0;
	if(t1&&(!t2||R[t1]<R[t2]))return R[t1]==R[x]?Q(t1):Q(t1)+1;
	return R[t2]==R[x]?Q(t2):Q(t2)+1;
	
}

void add(int x,int f){
	T.a=1,T.b=x-1,T.c=R[x];
	int t1=T.a<=T.b?T.find_L(1,1,n):0;
	if(!t1||R[t1]>R[x]){
		T.a=t1+1,T.b=x-1,T.c=f;
		if(T.a<=T.b)T.add(1,1,n);
	} 
	
	T.a=x+1,T.b=n,T.c=R[x];
	int t2=T.a<=T.b?T.find_R(1,1,n):0;
		
	if(!t2)t2=n+1;
	if(t2==n+1||R[t2]>R[x]){
		T.a=x+1,T.b=t2-1,T.c=f;
		if(T.a<=T.b)T.add(1,1,n);
	}
}
 
int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
//char S[100];
int main(){
//	int cases=read();
//	sprintf(S,"ex_summer%d.in",cases);
//	freopen(S,"r",stdin);
//	sprintf(S,"ex_summer%d.out",cases);
//	freopen(S,"w",stdout);
	freopen("summer.in","r",stdin);
	freopen("summer.out","w",stdout);
	n=read(),k=read();
	rep(i,n)R[i]=read();
	init();T.build(1,1,n);
	int Q=read();while(Q--){
		int x=read(),l=read(),r=read();
		if(R[x]!=R[x+1]){
			add(x,-1),add(x+1,-1);
			T.a=x,T.c=R[x+1];T.change(1,1,n);
			T.a=x+1,T.c=R[x];T.change(1,1,n);
			swap(R[x],R[x+1]);
			add(x,1),add(x+1,1);
			int t1=x,t2=x+1;
			if(R[t1]<R[t2])swap(t1,t2);
			T.c=cal(t1);T.a=t1;T.set(1,1,n);
			T.c=cal(t2);T.a=t2;T.set(1,1,n);
		}
		T.a=l,T.b=r;
		ll ans=T.sum(1,1,n);
		printf("%lld\n",ans*k+1ll*(n-1)*(r-l+1));
	}
	return 0;
}
